package math.leetcode_229;

import java.util.ArrayList;
import java.util.List;

public class MooreSolution {
    public List<Integer> majorityElement(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int record1 = nums[0];
        int record2 = nums[0];
        int count1 = 0;
        int count2 = 0;
        // 投票阶段
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == record1) {
                count1++;
                continue;
            }
            if (nums[i] == record2) {
                count2++;
                continue;
            }
            if (count1 == 0) {
                record1 = nums[i];
                count1++;
                continue;
            }
            if (count2 == 0) {
                record2 = nums[i];
                count2++;
                continue;
            }
            // 都不匹配
            count1--;
            count2--;
        }
        /*
            重新计数，长度为 N 的数组中获得大于 N/3 的票的人最多只能有两个
                上述过程只得到了两个候选人，但无法保证获得票数一定大于 N/3
         */
        count1 = 0;
        count2 = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == record1) {
                count1++;
            } else if (nums[i] == record2) {
                count2++;
            }
        }
        if (count1 > nums.length / 3) {
            res.add(record1);
        }
        if (count2 > nums.length / 3) {
            res.add(record2);
        }
        return res;
    }
}
